package com.jdaw.datastructure.linkedlist;

public class Josephu {
    public static void main(String[] args) {
        CircleSingleLinkedList circleSingleLinkedList=new CircleSingleLinkedList();
        circleSingleLinkedList.addBoy(5);
        circleSingleLinkedList.countBoy(1,2,5);
    }
}

//创建环形单向链表
class CircleSingleLinkedList{
    private Boy first=new Boy(-1);

    //添加小孩开始构建
    public void addBoy(int num){
        if(num<=0){
            System.out.println("num值不正确");
        }
        Boy curBoy=null;//辅助指针帮助构建环形链表
        for(int i=1;i<=num;i++){
            Boy boy=new Boy(i);
            if(i==1){
                first=boy;
                first.setNext(first);
                curBoy=first;//first不能动
            }else{
                curBoy.setNext(boy);
                boy.setNext(first);
                curBoy=boy;
            }
        }
    }

    //节点出圈
    //1.辅助指针helper等于first,然后指向最后一个节点；2.报数前让first，helper，先移动k-1次，再同时移动m-1次；3.让helper指针指向的节点出圈
    /*
    * @param countNum 数几下
    * @param startNo 从第几个小孩开始数
    * @param nums 一开始有多少个小孩在圈内
    * */
    public void countBoy(int startNo,int countNum,int nums){

        if(startNo<1||startNo>nums||first==null){
            System.out.println("参数输入有误，请重新输入");
            return;
        }
        Boy helper=first;
        while(true){
            if(helper.getNext()==first){
                break;
            }
            helper=helper.getNext();
        }
        for(int i=0;i<startNo-1;i++){
            helper=helper.getNext();
            first=first.getNext();
        }
        //不断循环出圈，直到圈中只有一个人
        while(helper!=first){
            for(int i=0;i<countNum-1;i++){
                helper=helper.getNext();
                first=first.getNext();
            }
            //此时first指向了要出圈的小孩
            System.out.printf("小孩%d出圈\n",first.getNo());
            first=first.getNext();
            helper.setNext(first);
        }
    }

    //遍历当前的环形链表，让curBoy往后走
    public void showBoy(){
        if(first==null){
            System.out.println("链表为空");
        }
        Boy curBoy=first;//辅助指针帮助遍历环形链表
        while(true){
            System.out.println(curBoy.getNo());
            if(curBoy.getNext()==first){
                break;
            }
            curBoy=curBoy.getNext();
        }
    }
}

//创建一个Boy类，表示一个节点
class Boy{
    private int no;
    private Boy next;
    public Boy(int no){
        this.no=no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }
}